package com.ljy.my_study.leetcode.连接词;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TestMain {

//    给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。
//
//    连接词 定义为：一个完全由给定数组中的至少两个较短单词组成的字符串。
//
//
//
//    示例 1：
//
//    输入：words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
//    输出：["catsdogcats","dogcatsdog","ratcatdogcat"]
//    解释："catsdogcats" 由 "cats", "dog" 和 "cats" 组成;
//     "dogcatsdog" 由 "dog", "cats" 和 "dog" 组成;
//     "ratcatdogcat" 由 "rat", "cat", "dog" 和 "cat" 组成。
//
//    示例 2：
//
//    输入：words = ["cat","dog","catdog"]
//    输出：["catdog"]
//
//
//
//    提示：
//
//            1 <= words.length <= 104
//            0 <= words[i].length <= 1000
//    words[i] 仅由小写字母组成
//    0 <= sum(words[i].length) <= 105
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/concatenated-words
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        String[] words={"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"};
        System.out.println(new TestMain().findAllConcatenatedWordsInADict(words));
    }
//    字典树+dfs
    private Trie trie=new Trie();
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Arrays.sort(words,(a,b)->a.length()-b.length());
        List<String> result=new ArrayList<>();
        for(String w:words){
            if(w.length()==0){
                continue;
            }
            if(dfs(w,0,0)){
                result.add(w);
            }else{
                insert(w);
            }
        }
        return result;
    }

    private void insert(String w){
        char[] chars=w.toCharArray();
        Trie next=trie;
        for(int i=0;i<chars.length;i++){
            char c=chars[i];
            Trie nextNext=next.next[c-'a'];
            if(nextNext==null){
                nextNext=new Trie();
                next.next[c-'a']=nextNext;
            }
            if(i==chars.length-1){
                nextNext.end=true;
            }
            next=nextNext;
        }
    }

    private boolean dfs(String word,int start,int count){
        char[] chars=word.toCharArray();
        if(start==chars.length&&count>1){
            return true;
        }
        Trie node=trie;
        for(int i=start;i<chars.length;i++){
            int index=chars[i]-'a';
            Trie next=node.next[index];
            if(next==null){
                return false;
            }
            if(next.end){
                if(dfs(word,i+1,count+1)){
                    return true;
                }
            }
            node=next;
        }
        return false;
    }

    public static class Trie{
        public Trie[] next;
        public boolean end;

        public Trie(){
            next=new Trie[26];
            end=false;
        }
    }
}
